package com.person.leetcode.editor.cn;

/**
 * 34.在排序数组中查找元素的第一个和最后一个位置
 * 2022-10-10 10:44:17
 **/
public class Sequence_0034_FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new Sequence_0034_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        int i = solution.binarySearch(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 4);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) return new int[]{-1, -1};
            //两次二分查找,找到前面的和后面的
            int flag = binarySearch(nums, target),left = -1,right = -1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target){
                    right = i;
                }
            }
            for (int i = nums.length-1; i > -1; i--) {
                if (nums[i] == target){
                    left = i;
                }
            }
            return new int[]{left,right};

//            int left = binarySearchLeft(nums,target);
//            int right = binarySearchRight(nums,target)-1;
//            System.out.println(left);
//            System.out.println(right);
//            if (left <= right && nums[left] == target && nums[right] == target){
//                return new int[]{left,right};
//            }
//
//            return new int[]{-1,-1};


        }

        //二分法边界 有边界
        private int binarySearchRight(int[] nums, int target) {
            int first = 0, end = nums.length - 1, ans = -1;
            while (first <= end) {
                int mid = (first + end) / 2;
                if (nums[mid] > target) {
                    end = mid - 1;
                } else {
                    first = mid + 1;
                }
                ans = mid;
            }
            return ans;
        }

        //左边界
        private int binarySearchLeft(int[] nums, int target) {
            int first = 0, end = nums.length - 1, ans = -1;
            while (first <= end) {
                int mid = (first + end) / 2;
                if (nums[mid] >= target) {
                    end = mid - 1;
                } else {
                    first = mid + 1;
                }
                ans = mid;
            }
            return ans;
        }

        //二分法
        private int binarySearch(int[] nums, int target) {
            int first = 0, end = nums.length - 1, ans = -1;
            while (first <= end) {
                int mid = (first + end) / 2;
                if (nums[mid] > target) {
                    end = mid - 1;
                } else if (nums[mid] < target) {
                    first = mid + 1;
                } else {
                    return mid;
                }

            }
            return -1;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}